package com.leetcode.partition2;

import com.leetcode.common.TreeNode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/19 8:22
 */
public class LC112路径总和 {

    public static boolean hasPathSum(TreeNode root, int targetSum) {
//        return backtracking(root, targetSum, 0);
        return iteration(root, targetSum);
    }

    public static void main(String[] args) {
        TreeNode r1 = new TreeNode(-2, null, new TreeNode(-3));
        System.out.println(hasPathSum(r1, -6));
    }

    private static boolean iteration(TreeNode root, final int targetSum) {
        Stack<TreeNodeSum> s = new Stack<>();
        s.add(new TreeNodeSum(root, root.val));
        while (!s.isEmpty()) {
            TreeNodeSum cur = s.pop();
            if (cur.node.left == null && cur.node.right == null && cur.sum == targetSum) return true;
            if (cur.node.right != null) s.push(new TreeNodeSum(cur.node.right, cur.sum + cur.node.right.val));
            if (cur.node.left != null) s.push(new TreeNodeSum(cur.node.left, cur.sum + cur.node.left.val));
        }
        return false;
    }

    private static boolean backtracking(TreeNode root, final int targetSum, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == sum + root.val;
        return backtracking(root.left, targetSum, sum + root.val) || backtracking(root.right, targetSum, sum + root.val);
    }

    private static class TreeNodeSum {
        TreeNode node;
        int sum;

        public TreeNodeSum(TreeNode node, int sum) {
            this.node = node;
            this.sum = sum;
        }
    }
}
